package com.demo02.offer25.PathInTree;

import java.util.Stack;
import java.util.Vector;

/**
 * 输入一个整数和一颗二叉树。从树的根节点开始往下访问一直到叶结点所经过的结点
 * 形成一条路径。打印出和与输入整数相等的所有路径。
 * 要求：  无
 * 注：   二叉树结点的值不一定有序，极端情况下所有节点都要遍历到
 */
public class Main {
    // 1
    public static void getPathOfBTree(int num, Node tree) {
        pathOfBTree(num, tree, "");
    }

    // 1
    public static void pathOfBTree(int num, Node tree, String path) {
        if (tree == null || tree.getValue() > num) {
            return;
        }
        if (tree.getLeft() == null && tree.getRight() == null && tree.getValue() == num) {
            System.out.println(path + tree.getValue());
            return;
        }
        pathOfBTree(num - tree.getValue(), tree.getLeft(), path + tree.getValue() + " ");
        pathOfBTree(num - tree.getValue(), tree.getRight(), path + tree.getValue() + " ");
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        Node n2 = new Node(5);
        Node n3 = new Node(12);
        Node n4 = new Node(4);
        Node n5 = new Node(7);
        root.setLeft(n2);
        root.setRight(n3);
        n2.setLeft(n4);
        n2.setRight(n5);

        //Main.getPathOfBTree(22, root);
        findPath(root,22);
    }

    /**
     * 2
     */
    static  void findPath(Node root,int expectedNum){
        if(root == null){
            return;
        }
        Stack<Integer> path = new Stack<>();
        int currentSum=0;
        findPath(root,expectedNum,path,currentSum);
    }
    static void findPath(Node root, int exceptedNum, Stack<Integer> path, int currentSum) {
        currentSum += root.getValue();
        path.push(root.getValue());
        boolean isLeaf = root.getLeft() == null && root.getRight() == null;
        if (currentSum == exceptedNum && isLeaf) {
            for (Integer a : path) {
                System.out.print(a + " ");
            }
            System.out.println();
        }
        if(root.getLeft()!=null){
            findPath(root.getLeft(),exceptedNum,path,currentSum);
        }
        if(root.getRight()!=null){
            findPath(root.getRight(),exceptedNum,path,currentSum);
        }
        path.pop();
    }
}

class Node {
    private int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }
}